/*
 * Copyright (c) 2019 Wormpex.com. All Rights Reserved.
 */

package com.sk.leetcode.arithmetic;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ke.su date: 2019-06-13 Time: 下午2:09
 * 二叉搜索树中的两个节点被错误地交换。
 * <p>
 * 请在不改变其结构的情况下，恢复这棵树。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,3,null,null,2]
 * <p>
 *    1
 *   /
 *  3
 *   \
 *    2
 * <p>
 * 输出: [3,1,null,null,2]
 * <p>
 *    3
 *   /
 *  1
 *   \
 *    2
 * 示例 2:
 * <p>
 * 输入: [3,1,4,null,null,2]
 * <p>
 * 3
 * / \
 * 1   4
 *    /
 *   2
 * <p>
 * 输出: [2,1,4,null,null,3]
 * <p>
 * 2
 * / \
 * 1   4
 *    /
 *  3
 * 进阶:
 * <p>
 * 使用 O(n) 空间复杂度的解法很容易实现。
 * 你能想出一个只使用常数空间的解决方案吗？
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/recover-binary-search-tree
 * <p>
 * <p>
 * 中序排序，错误值互换
 */
public class Test99 {

    public static void main(String[] args) {

        Integer[] root = {3, 1, 4, null, null, 2, null};
        //Integer[] root = {1, 3, null, null, 2, null, null};

        List<TreeNode> nodes = Test124.suan(root);

        recoverTree(nodes.get(0));


    }


    public static void recoverTree(TreeNode root) {
        List<TreeNode> minList = new ArrayList<>();
        //中序排序
        midOrder(root, minList);
        System.out.println();

        TreeNode one = null;
        //纠错
        //顺序排序,因为只有一对数据错误，所以只需要查找到，比前面的值最小的一个值交换就会恢复
        for (int i = 0; i < minList.size(); i++) {
            //注意点，一定从当前向后查找
            for (int j = i; j < minList.size(); j++) {
                if(minList.get(i).val > minList.get(j).val) {
                    if(one == null) {
                        one = minList.get(j);
                    }
                    if(one.val > minList.get(j).val) {
                        one = minList.get(j);
                    }
                }
            }
            if(one == null) {
                continue;
            }
            int var = one.val;

            one.val = minList.get(i).val;

            minList.get(i).val = var;
            break;
        }


        //重排，重看结果
        midOrder(root, minList);
        System.out.println();

    }

    private static void midOrder(TreeNode node, List<TreeNode> list) {
        if(node == null) {
            return;
        } else {
            midOrder(node.left, list);
            list.add(node);
            System.out.print(node.val);
            midOrder(node.right, list);
        }

    }


}
